package AlgorithmTest;

public class Merge_Sort {
	
    public int[] sort(int[] input) {
        if (input.length <= 1) return input;
        if (input.length == 2) {
            if (input[0] > input[1]) {
                int temp = input[0];
                input[0] = input[1];
                input[1] = temp;
            }
            return input;
        }
        int mid = input.length / 2;
        int[] firstHalf = sort(getPart(input, 0, mid));
        int[] secondHalf = sort(getPart(input, mid + 1, input.length - 1));
        return mergePart(firstHalf, secondHalf);
    }

    private int[] mergePart(int[] firstHalf, int[] secondHalf) {
        int[] result = new int[firstHalf.length + secondHalf.length];
        int firstIndex = 0, secondIndex = 0, resultIndex = 0;
        while (resultIndex < result.length) {
            if (chooseFirstHalf(firstHalf, firstIndex, secondHalf, secondIndex))
                result[resultIndex++] = firstHalf[firstIndex++];
            else
                result[resultIndex++] = secondHalf[secondIndex++];
        }
        return result;
    }

    private boolean chooseFirstHalf(int[] firstHalf, int firstIndex, int[] secondHalf, int secondIndex) {
        if (firstIndex == firstHalf.length) return false;
        if (secondIndex == secondHalf.length) return true;
        return firstHalf[firstIndex] < secondHalf[secondIndex];
    }

    private int[] getPart(int[] input, int begin, int end) {
        int[] result = new int[end - begin + 1];
        for (int i = begin; i <= end; i++) result[i - begin] = input[i];
        return result;
    }
    
    public static void main(String[] args) {
		Merge_Sort m=new Merge_Sort();
		int[] input={3,2,1,4,6,7,8,5};
		m.sort(input);
	}
}
